package algorithm.graph.adjacencymatrix;

import java.util.*;

public class Dijkstra {
    AdjacencyMatrixGraph graph;

    public Dijkstra(AdjacencyMatrixGraph graph) {
        this.graph = graph;
    }

    public Map<Integer, List<Integer>> findShortestPath(int startNode) {
        List<PathNode> visitedPathNodeList = new ArrayList<>();
        visitedPathNodeList.add(new PathNode(startNode, null, 0));
        List<PathNode> unvisitedPathNodeList = new ArrayList<>();
        for (int i = 0; i < graph.getNodeCount(); i++) {
            if (i != startNode) {
                unvisitedPathNodeList.add(new PathNode(i, null, -1));
            }
        }
        while (!unvisitedPathNodeList.isEmpty()) {
            PathNode nextPathNode = findNextPathNode(graph, visitedPathNodeList, unvisitedPathNodeList);
            System.out.println("nextPathNode = " + nextPathNode);
            if (nextPathNode != null) {
                visitedPathNodeList.add(nextPathNode);
                unvisitedPathNodeList.remove(nextPathNode);
            } else {
                unvisitedPathNodeList.remove(0);
            }
        }
        Map<Integer, List<Integer>> pathList = new HashMap<>();
        for (PathNode pathNode : visitedPathNodeList) {
            PathNode temp = pathNode;
            if (temp.minPathLength != -1) {
                List<Integer> path = new ArrayList<>();
                while (temp != null) {
                    path.add(temp.nodeId);
                    temp = temp.parent;
                }
                pathList.put(pathNode.nodeId, path);
            }
        }
        return pathList;
    }

    private PathNode findNextPathNode(AdjacencyMatrixGraph graph, List<PathNode> visitedPathNodeList, List<PathNode> unvisitedPathNodeList) {
        PathNode nextPathNode = null;
        int[][] graphData = graph.getGraphData();
        for (PathNode unvisitedPathNode : unvisitedPathNodeList) {
            PathNode visitedPathNode = visitedPathNodeList.get(visitedPathNodeList.size()-1);
            if(visitedPathNode!=null){
                if (graphData[visitedPathNode.nodeId][unvisitedPathNode.nodeId] != -1) {
                    int newPathLength = visitedPathNode.minPathLength + graphData[visitedPathNode.nodeId][unvisitedPathNode.nodeId];
                    if (unvisitedPathNode.minPathLength == -1 || newPathLength < unvisitedPathNode.minPathLength) {
                        unvisitedPathNode.minPathLength = newPathLength;
                        unvisitedPathNode.parent = visitedPathNode;
                    }
                }
            }
            if (nextPathNode == null) {
                nextPathNode = unvisitedPathNode;
            } else if (nextPathNode.minPathLength < unvisitedPathNode.minPathLength) {
                nextPathNode = unvisitedPathNode;
            }
        }
        return nextPathNode;
    }

    public static class PathNode {
        int nodeId;
        PathNode parent;
        int minPathLength;

        public PathNode(int nodeId, PathNode parent, int minPathLength) {
            this.nodeId = nodeId;
            this.parent = parent;
            this.minPathLength = minPathLength;
        }

        public int getNodeId() {
            return nodeId;
        }

        public void setNodeId(int nodeId) {
            this.nodeId = nodeId;
        }

        public PathNode getParent() {
            return parent;
        }

        public void setParent(PathNode parent) {
            this.parent = parent;
        }

        public int getMinPathLength() {
            return minPathLength;
        }

        public void setMinPathLength(int minPathLength) {
            this.minPathLength = minPathLength;
        }

        @Override
        public String toString() {
            return "PathNode{" +
                    "nodeId=" + nodeId +
                    ", minLength=" + minPathLength +
                    '}';
        }
    }

}
